Geometric Methods for Feature Extraction and Dimensional Reduction %2D A Guided Tour.
Abstract We give a tutorial overview of several geometric methods for feature extraction and dimensional reduction. We divide the methods into projective methods and methods that model the manifold on which the data lies. For projective methods, we review projection pursuit, principal component analysis (PCA), kernel PCA, probabilistic PCA, and oriented PCA; and for the manifold methods, we review multidimensional scaling (MDS), landmark MDS, Isomap, locally linear embedding, Laplacian eigenmaps and spectral clustering. The Nyström method, which links several of the algorithms, is also reviewed. The goal is to provide a self-contained review of the concepts and mathematics underlying these algorithms.
Dimension Reduction A Guided Tour.
We give a tutorial overview of several foundational methods for dimension reduction. We divide the methods into projective methods and methods that model the manifold on which the data lies. For projective methods, we review projection pursuit, principal component analysis (PCA), kernel PCA, probabilistic PCA, canonical correlation analysis (CCA), kernel CCA, Fisher discriminant analysis, oriented PCA, and several techniques for sufficient dimension reduction. For the manifold methods, we review multidimensional scaling (MDS), landmark MDS, Isomap, locally linear embedding, Laplacian eigenmaps, and spectral clustering. Although the review focuses on foundations, we also provide pointers to some more modern techniques. We also describe the correlation dimension as one method for estimating the intrinsic dimension, and we point out that the notion of dimension can be a scale-dependent quantity. The Nyström method, which links several of the manifold algorithms,
Adapting boosting for information retrieval measures.
Abstract We present a new ranking algorithm that combines the strengths of two previous methods: boosted tree classification, and LambdaRank, which has been shown to be empirically optimal for a widely used information retrieval measure. Our algorithm is based on boosted regression trees, although the ideas apply to any weak learners, and it is significantly faster in both train and test phases than the state of the art, for comparable accuracy. We also show how to find the optimal linear combination for any two rankers, and we use this method to solve the line search problem exactly during boosting. In addition, we show that starting with a previously trained model, and boosting using its residuals, furnishes an effective technique for model adaptation, and we give significantly improved results for a particularly pressing problem in Web Search- training rankers for markets for which only small amounts of labeled data are available, given a ranker trained on much more data from a larger market.
A machine learning approach for improved BM25 retrieval.
Despite the widespread use of BM25, there have been few studies examining its effectiveness on a document description over single and multiple field combinations. We determine the effectiveness of BM25 on various document fields. We find that BM25 models relevance on popularity fields such as anchor text and query click information no better than a linear function of the field attributes. We also find query click information to be the single most important field for retrieval. In response, we develop a machine learning approach to BM25-style retrieval that learns, using LambdaRank, from the input attributes of BM25. Our model significantly improves retrieval effectiveness over BM25 and BM25F. Our data-driven approach is fast, effective, avoids the problem of parameter tuning, and can directly optimize for several common information retrieval measures. We demonstrate the advantages of our model on a very large real-world Web data collection.
Model Adaptation via Model Interpolation and Boosting for Web Search Ranking.
This paper explores two classes of model adaptation methods for Web search ranking: Model Interpolation and error-driven learning approaches based on a boosting algorithm. The results show that model interpolation, though simple, achieves the best results on all the open test sets where the test data is very different from the training data. The tree-based boosting algorithm achieves the best performance on most of the closed test sets where the test data and the training data are similar, but its performance drops significantly on the open test sets due to the instability of trees. Several methods are explored to improve the robustness of the algorithm, with limited success. 1
On the local optimality of LambdaRank.
A machine learning approach to learning to rank trains a model to optimize a target evaluation measure with repect to training data. Currently, existing information retrieval measures are impossible to optimize directly except for models with a very small number of parameters. The IR community thus faces a major challenge: how to optimize IR measures of interest directly. In this paper, we present a solution. Specifically, we show that LambdaRank [1], which smoothly approximates the gradient of the target measure, can be adapted to work with four popular IR target evaluation measures using the same underlying gradient construction. It is likely, therefore, that this construction is extendable to other evaluation measures. We empirically show that LambdaRank finds a locally optimal solution for mean NDCG@10, mean NDCG, MAP and MRR with a 99% confidence rate. We also show that the amount of effective training data varies with IR measure and that with a sufficiently large training set size, matching the training optimization measure to the target evaluation measure yields the best accuracy.
Using Signals of Human Interest to Enhance Single%2Ddocument Summarization.
As the amount of information on the Web grows, the ability to retrieve relevant information quickly and easily is necessary. The combination of ample news sources on the Web, little time to browse news, and smaller mobile devices motivates the development of automatic highlight extraction from single news articles. Our system, NetSum, is the first system to produce highlights of an article and significantly outperform the baseline. Our approach uses novel information sources to exploit human interest for highlight extraction. In this paper, we briefly describe the novelties of NetSum, originally presented at EMNLP 2007, and embed our work in the AI context.
Improving Web Spam Classification using Rank%2Dtime Features.
In this paper, we study the classification of web spam. Web spam refers to pages that use techniques to mislead search engines into assigning them higher rank, thus increasing their site traffic. Our contributions are two fold. First, we find that the method of dataset construction is crucial for accurate spam classification and we note that this problem occurs generally in learning problems and can be hard to detect. In particular, we find that ensuring no overlapping domains between test and training sets is necessary to accurately test a web spam classifier. In our case, classification performance can differ by as much as 40 % in precision when using non-domain-separated data. Second, we show ranktime features can improve the performance of a web spam classifier. Our paper is the first to investigate the use of rank-time features, and in particular query-dependent ranktime features, for web spam detection. We show that the use of rank-time and query-dependent features can lead to an increase in accuracy over a classifier trained using page-based content only. 
Transductive Link Spam Detection.

Spectral clustering and transductive learning with multiple views.
We consider spectral clustering and transductive inference for data with multiple views. A typical example is the web, which can be described by either the hyperlinks between web pages or the words occurring in web pages. When each view is represented as a graph, one may convexly combine the weight matrices or the discrete Laplacians for each graph, and then proceed with existing clustering or classification techniques. Such a solution might sound natural, but its underlying principle is not clear. Unlike this kind of methodology, we develop multiview spectral clustering via generalizing the normalized cut from a single view to multiple views. We further build multiview transductive inference on the basis of multiview spectral clustering. Our framework leads to a mixture of Markov chains defined on every graph. The experimental evaluation on real-world web classification demonstrates promising results that validate our method. 1.
Enhancing Single%2DDocument Summarization by Combining RankNet and Third%2DParty Sources.
We present a new approach to automatic summarization based on neural nets, called NetSum. We extract a set of features from each sentence that helps identify its importance in the document. We apply novel features based on news search query logs and Wikipedia entities. Using the RankNet learning algorithm, we train a pair-based sentence ranker to score every sentence in the document and identify the most important sentences. We apply our system to documents gathered from CNN.com, where each document includes highlights and an article. Our system significantly outperforms the standard baseline in the ROUGE-1 measure on over 70 % of our document set. 1
Spectral clustering and transductive learning with multiple views.
We consider spectral clustering and transductive inference for data with multiple views. A typical example is the web, which can be described by either the hyperlinks between web pages or the words occurring in web pages. When each view is represented as a graph, one may convexly combine the weight matrices or the discrete Laplacians for each graph, and then proceed with existing clustering or classification techniques. Such a solution might sound natural, but its underlying principle is not clear. Unlike this kind of methodology, we develop multiview spectral clustering via generalizing the normalized cut from a single view to multiple views. We further build multiview transductive inference on the basis of multiview spectral clustering. Our framework leads to a mixture of Markov chains defined on every graph. The experimental evaluation on real-world web classification demonstrates promising results that validate our method. 1.
McRank Learning to Rank Using Multiple Classification and Gradient Boosting.
We cast the ranking problem as (1) multiple classification (“Mc”) (2) multiple ordinal classification, which lead to computationally tractable learning algorithms for relevance ranking in Web search. We consider the DCG criterion (discounted cumulative gain), a standard quality measure in information retrieval. Our approach is motivated by the fact that perfect classifications result in perfect DCG scores and the DCG errors are bounded by classification errors. We propose using the Expected Relevance to convert class probabilities into ranking scores. The class probabilities are learned using a gradient boosting tree algorithm. Evaluations on large-scale datasets show that our approach can improve LambdaRank [5] and the regressions-based ranker [6], in terms of the (normalized) DCG scores. An efficient implementation of the boosting tree algorithm is also presented. 1
Question Answering over Implicitly Structured Web Content.
Implicitly structured content on the Web such as HTML tables and lists can be extremely valuable for web search, question answering, and information retrieval, as the implicit structure in a page often reflects the underlying semantics of the data. Unfortunately, exploiting this information presents significant challenges due to the immense amount of implicitly structured content on the web, lack of schema information, and unknown source quality. We present TQA, a web-scale system for automatic question answering that is often able to find answers to real natural language questions from the implicitly structured content on the web. Our experiments over more than 200 million structures extracted from a partial web crawl demonstrate the promise of our approach. 1
Optimisation methods for ranking functions with multiple parameters.
parameters
Learning to Rank with Nonsmooth Cost Functions.

High accuracy retrieval with multiple nested ranker.
High precision at the top ranks has become a new focus of research in information retrieval. This paper presents the multiple nested ranker approach that improves the accuracy at the top ranks by iteratively re-ranking the top scoring documents. At each iteration, this approach uses the RankNet learning algorithm to re-rank a subset of the results. This splits the problem into smaller and easier tasks and generates a new distribution of the results to be learned by the algorithm. We evaluate this approach using different settings on a data set labeled with several degrees of relevance. We use the normalized discounted cumulative gain (NDCG) to measure the performance because it depends not only on the position but also on the relevance score of the document in the ranked list. Our experiments show that making the learning algorithm concentrate on the top scoring results improves precision at the top ten documents in terms of the NDCG score.
Learning to rank using gradient descent.
We investigate using gradient descent methods for learning ranking functions; we propose a simple probabilistic cost function, and we introduce RankNet, an implementation of these ideas using a neural network to model the underlying ranking function. We present test results on toy data and on data from a commercial internet search engine. 1.
Inferring similarity between music objects with application to playlist generation.

Geometric Methods for Feature Extraction and Dimensional Reduction %2D A Guided Tour.
Abstract We give a tutorial overview of several geometric methods for feature extraction and dimensional reduction. We divide the methods into projective methods and methods that model the manifold on which the data lies. For projective methods, we review projection pursuit, principal component analysis (PCA), kernel PCA, probabilistic PCA, and oriented PCA; and for the manifold methods, we review multidimensional scaling (MDS), landmark MDS, Isomap, locally linear embedding, Laplacian eigenmaps and spectral clustering. The Nyström method, which links several of the algorithms, is also reviewed. The goal is to provide a self-contained review of the concepts and mathematics underlying these algorithms.
Geometric Methods for Feature Extraction and Dimensional Reduction %2D A Guided Tour.
Abstract We give a tutorial overview of several geometric methods for feature extraction and dimensional reduction. We divide the methods into projective methods and methods that model the manifold on which the data lies. For projective methods, we review projection pursuit, principal component analysis (PCA), kernel PCA, probabilistic PCA, and oriented PCA; and for the manifold methods, we review multidimensional scaling (MDS), landmark MDS, Isomap, locally linear embedding, Laplacian eigenmaps and spectral clustering. The Nyström method, which links several of the algorithms, is also reviewed. The goal is to provide a self-contained review of the concepts and mathematics underlying these algorithms.
Redundant Bit Vectors for Quickly Searching High%2DDimensional Regions.
Abstract. Applications such as audio fingerprinting require search in high dimensions: find an item in a database that is similar to a query. An important property of this search task is that negative answers are very frequent: much of the time, a query does not correspond to any database item. We propose Redundant Bit Vectors (RBVs):anovelmethodforquickly solving this search problem. RBVs rely on three key ideas: 1) approximate the high-dimensional regions/distributions as tightened hyperrectangles, 2) partition the query space to store each item redundantly in an index and 3) use bit vectors to store and search the index efficiently. We show that our method is the preferred method for very large databases or when the queries are often not in the database. Our method is 109 times faster than linear scan, and 48 times faster than localitysensitive hashing on a data set of 239369 audio fingerprints. 1
Identifying audio clips with RARE.

Some Notes on Applied Mathematics for Machine Learning.
This chapter 1 describes Lagrange multipliers and some selected subtopics from matrix analysis from a machine learning perspective. The goal is to give a detailed description of a number of mathematical constructions that are widely used in applied machine learning.
Image compression with on%2Dline and off%2Dline learning.
Images typically contain smooth regions, which are easily compressed by linear transforms, and high activity regions (edges, textures), which are harder to compress. To compress the first kind, we use a &#034;zero&#034; encoder that has infinite context, very low capacity, and which adapts very quickly to the content. For the second, we use an &#034;interpolation &#034; encoder, based on neural networks, which has high capacity, a finite-size context, and is trained off-line. The two encoders can be used separately or in combination. The zero-encoder surpasses JPEG2000 by 3.5% in overall compression, even though it is less efficient in high activity regions. Thanks to off-line training, the interpolation-encoder predicts high activity regions well, so it also matches the performance of JPEG2000, even though it does not use an arithmetic encoder and is less efficient in low activity regions. In both cases it is surprising that we match the stateof -the-art in image compression without using adaptive arithmetic  encoding.
Distortion discriminant analysis for audio fingerprinting.
this paper presents a system that reduces the input dimensionality by a factor of approximately 8,000. Second, the resulting features must be robust to likely distortions of the input: for example, most radio stations introduce nonlinear distortions into the signal before broadcasting. Third, the resulting features must be informative: for audio identification, di#erent audio clips should map to features that are distant, in some suitable metric. Fourth, the feature extraction operation must be computationally effecient: we require that it use a small fraction of the resources available on a typical PC
Uniqueness theorems for kernel methods.

Editorial Kernel Methods Current Research and Future Directions.

Improving Wavelet Compression with Neural Networks.

Learning a Gaussian Process Prior for Automatically Generating Music Playlists.
This paper presents AutoDJ: a system for automatically generating music playlists based on one or more seed songs selected by a user. AutoDJ uses Gaussian Process Regression to learn a user preference function over songs. This function takes music metadata as inputs. This paper further introduces Kernel Meta-Training, which is a method of learning a Gaussian Process kernel from a distribution of functions that generates the learned function. For playlist generation, AutoDJ learns a kernel from a large set of albums. This learned kernel is shown to be more effective at predicting users&#039; playlists than a reasonable hand-designed kernel.
Uniqueness of the SVM Solution.
We give necessary and sufficient conditions for uniqueness of the  support vector solution for the problems of pattern recognition and  regression estimation, for a general class of cost functions. We show  that if the solution is not unique, all support vectors are necessarily  at bound, and we give some simple examples of non-unique solutions.  We note that uniqueness of the primal (dual) solution does  not necessarily imply uniqueness of the dual (primal) solution. We  show how to compute the threshold b when the solution is unique,  but when all support vectors are at bound, in which case the usual  method for determining b does not work.  1 Introduction  Support vector machines (SVMs) have attracted wide interest as a means to implement structural risk minimization for the problems of classification and regression estimation. The fact that training an SVM amounts to solving a convex quadratic programming problem means that the solution found is global, and that if it is not unique...
Input space versus feature space in kernel%2Dbased methods.
This paper collects some ideas targeted at advancing our understanding of the feature spaces associated with support vector (SV) kernel functions. We first discuss the geometry of feature space. In particular, we review what is known about the shape of the image of input space under the feature space map, and how this influences the capacity of SV methods. Following this, we describe how the metric governing the intrinsic geometry of the mapped surface can be computed in terms of the kernel, using the example of the class of inhomogeneous polynomial kernels, which are often used in SV pattern recognition. We then discuss the connection between feature space and input space by dealing with the question of how one can, given some vector in feature space, find a preimage (exact or approximate) in input space. We describe algorithms to tackle this issue, and show their utility in two applications of kernel methods. First, we use it to reduce the computational complexity of SV decision functions; second, we combine it with the Kernel PCA algorithm, thereby constructing a nonlinear statistical denoising technique which is shown to perform well on real-world data.
Fast Approximation of Support Vector Kernel Expansions

A Tutorial on Support Vector Machines for Pattern Recognition.
  The tutorial starts with an overview of the concepts of VC dimension and structural risk minimization. We then describe linear Support Vector Machines (SVMs) for separable and non-separable data, working through a non-trivial example in detail. We describe a mechanical analogy, and discuss when SVM solutions are unique and when they are global. We describe how support vector training can be practically implemented, and discuss in detail the kernel mapping technique which is used to construct SVM solutions which are nonlinear in the data. We show how Support Vector machines can have very large (even infinite) VC dimension by computing the VC dimension for homogeneous polynomial and Gaussian radial basis function kernels. While very high VC dimension would normally bode ill for generalization performance, and while at present there exists no theory which shows that good generalization performance is guaranteed for SVMs, there are several arguments which support the observed high accuracy of SVMs, which we review. Results of some experiments which were inspired by these arguments are also presented. We give numerous examples and proofs of most of the key theorems. There is new material, and I hope that the reader will find that even old material is cast in a fresh light.
Comparison of View%2DBased Object Recognition Algorithms Using Realistic 3D Models.
Abstract. Two view-based object recognition algorithms are compared: (1) a heuristic algorithm based on oriented lters, and (2) a support vector learning machine trained on low-resolution images of the objects. Classi cation performance is assessed using a high number of images generated by a computer graphics system under precisely controlled conditions. Training- and test-images show a set of 25 realistic threedimensional models of chairs from viewing directions spread over the upper half of the viewing sphere. The percentage of correct identi cation of all 25 objects is measured. In computer vision, view{based models of object recognition have become more and more in uential in recent years. Moreover, psychophysical evidence has been found for a view{based representation of objects in humans (Bultho and Edelman, 1992). Unlike viewpoint-invariant representations using structural descriptions (e.g. Marr and Nishihara, 1978), viewpoint-dependent models do not require a three-dimensional representation (Poggio, Edelman 1990, Lades et.al.,
Incorporating Invariances in Support Vector Learning Machines.
. Developed only recently, support vector learning machines achieve high generalization ability by minimizing a bound on the expected test error; however, so far there existed no way of adding knowledge about invariances of a classification problem at hand. We present a method of incorporating prior knowledge about transformation invariances by applying transformations to support vectors, the training examples most critical for determining the classification boundary. 1 Incorporating Invariances  in: C. von der Malsburg, W. von Seelen, J. C. Vorbruggen, &amp; B. Sendhoff (eds.): Artificial Neural Networks --- ICANN&#039;96. Springer Lecture Notes in Computer Science, Vol. 1112, Berlin, 1996, 47 --52 In many applications of learning procedures, prior knowledge about properties of the function to be learned is available (for a review, see Abu--Mostafa, 1995). For instance, certain transformations of the input could be known to leave function values unchanged. Mostly, two different ways of exploit...
Simplified Support Vector Decision Rules.
A Support Vector Machine (SVM) is a universal learning machine whose decision surface is parameterized by a set of support vectors, and by a set of corresponding weights. An SVM is also characterized by a kernel  function. Choice of the kernel determines whether the resulting SVM is a polynomial classifier, a two-layer neural network, a radial basis function machine, or some other learning machine. SVMs are currently considerably slower in test phase than other approaches with similar generalization performance. To address this, we present a general method to significantly decrease the complexity of the decision rule obtained using an SVM. The proposed method computes an approximation to the decision rule in terms of a reduced set of vectors. These reduced set vectors are not support vectors and can in some cases be computed analytically. We give experimental results for three pattern recognition problems. The results show that the method can decrease the computational complexity of th...
Support Vector Regression Machines.
A new regression technique based on Vapnik&#039;s concept of support vectors is introduced. We compare support vector regression (SVR) with a committee regression technique (bagging) based on regression trees and ridge regression done in feature space. On the basis of these experiments, it is expected that SVR will have advantages in high dimensionality space because SVR optimization does not depend on the dimensionality of the input space. 1. Introduction  In the following, lower case bold characters represent vectors and upper case bold characters represent matrices. Superscript &#034;t&#034; represents the transpose of a vector. y represents either a vector (in bold) or a single observance of the dependent variable in the presence of noise. y  (p)  indicates a predicted value due to the input vector xx  (p)  not seen in the training set. Suppose we have an unknown function G(xx) (the &#034;truth&#034;) which is a function of a vector  xx (termed input space). The vector xx  t  = [x 1 , x 2 , ..., x d ] has ...

Improving the Accuracy and Speed of Support Vector Machines.
Support Vector Learning Machines (SVM) are finding application in pattern recognition, regression estimation, and operator inversion for ill-posed problems. Against this very general backdrop, any methods for improving the generalization performance, or for improving the speed in test phase, of SVMs are of increasing interest. In this paper we combine two such techniques on a pattern recognition problem. The method for improving generalization performance (the &#034;virtual support vector&#034; method) does so by incorporating known invariances of the problem. This method achieves a drop in the error rate on 10,000 NIST test digit images of 1.4% to 1.0%. The method for improving the speed (the &#034;reduced set&#034; method) does so by approximating the support vector decision surface. We apply this method to achieve a factor of fifty speedup in test phase over the virtual support vector machine. The combined approach yields a machine which is both 22 times faster than the original machine, and which has ...

LeRec a NN%2FHMM hybrid for on%2Dline handwriting recognition.
We introduce a new approach for on-line recognition of handwritten words written in unconstrained mixed style. The preprocessor performs a word-level normalization by tting a model of the word structure using the EM algorithm. Words are then coded into low resolution \annotated images &amp;quot; where each pixel contains information about trajectory direction and curvature. The recognizer is a convolution network which can be spatially replicated. From the network output, a hidden Markov model produces word scores. The entire system is globally trained to minimize word-level errors. 1
Off Line Recognition of Handwritten Postal Words Using Neural Networks.

Reading Handwritten Digits A ZIP Code Recognition System.

Multi%2DDigit Recognition Using a Space Displacement Neural Network.
We present a feed-forward network architecture for recognizing an unconstrained handwritten multi-digit string. This is an extension of previous work on recognizing isolated digits. In this architecture a single digit recognizer is replicated over the input. The output layer of the network is coupled to a Viterbi alignment module that chooses the best interpretation of the input. Training errors are propagated through the Viterbi module. The novelty in this procedure is that segmentation is done on the feature maps developed in the Space Displacement Neural Network (SDNN) rather than the input (pixel) space. 1 Introduction  In previous work (Le Cun et al., 1990) we have demonstrated a feed-forward backpropagation network that recognizes isolated handwritten digits at state-of-the-art performance levels. The natural extension of this work is towards recognition of unconstrained strings of handwritten digits. The most straightforward solution is to divide the process into two: segmentati...
